1. Field of the Invention
The present invention relates to a delay management method and device which in an electronic computer enables read requests relating to data not yet stored in the computer memory to be delayed.
2. Description of Related Art
In an electronic computer, such as a microcomputer, when it is desired to access data stored in a memory device of the computer, a read request is made which indicates the specific memory addresses in which the data is stored. The stored data is then read out and processed as required. In existing serial processing computers it is not generally possible to access data which is not stored in the memory. In serial processing computers in which program commands are executed in individual independent devices, there are times when read requests are made which relate to data which has not yet reached the memory, and it is necessary to have a mechanism whereby the read request is delayed until the required data has reached the memory.
FIGS. 1a and 1b schematically illustrate a system incorporating such a delay management device, the system comprising a processing device and a memory device which has a facility to delay read requests (hereinafter referred to simply as a "read delay device"). A read delay device 100 is illustrated in FIG. 1a, the read delay device comprising a distribution (allocation) section 100a, a memory section 100b, a delay (defer) management section 100c and a clear control section 100d. Channels 101 and 102 are provided for sending information from processing device 103 to the read delay device 100 and from the read delay device 100 to the processing device 103 respectively.
The exchange of information between the processing device 103 and the read delay device 100 comprises the sending of a single data packet (herein referred to as a "token"). When the distribution section 100a receives a space request (SRQ) token 104 from the processing device 103 it returns a space provided (SP) token 107 comprising an address for the requested space. The memory section 100b also receives a write (WRT) token 105 and a read request (READ) token 106, in response to the former it enters a parameter V into an address A, and in response to the latter it reads the contents V of address A and sends the read data to the processing device 103 in the form of a data (DT) token 108. The significance of the data sent back is indicated by parameter Ra. Delay management section 100c and clear control section 100d do not communicate tokens directly to the processing device 103. Delay management section 100c manages read request tokens which relate to data which has not yet arrived in the memory section 100b, and clear control section 100 d clears memory areas which are no longer required. Each token is distinguished from the others by a code which forms a part of that token.
FIG. 1b shows the form of each token. The token forms identified by numerals 464 to 468 correspond to tokens 104 to 108 respectively in FIG. 1a.
It can be seen from FIG. 1b that each token comprises four fields, namely a first code field 451, a second code field 452, a third code field 453, and a fourth code field 454.
Code field 451 serves the purpose of distinguishing between the different kinds of tokens. In the example of FIG. 1b field 451 is allotted four bits, which can designate sixteen different kinds of token. For the sake of simplicity in the example shown the second, third and fourth fields 452 to 454 each have twenty four bits, but any number of bits can be allocated to each field depending on the requirements of the system. The shaded parts of the diagrams show fields which are not used in the tokens to which the diagrams relate.
FIGS. 2a, 2b and 2c serve to explain in detail the workings of memory section 100b and the delay management section 100c. In FIG. 2a numeral 100b denotes the memory section, and 201 and 202 are the entry and exit channels respectively of tokens going in and out of memory section 100b. The words inside memory section 100b contain a "flag field" and a "data field". The flag field of address A comprises a valid flag (P) 203 which shows whether or not there is any significant data in the data field and delay flag (D) 204 which shows whether or not a read request delay has occurred. That is to say when an entry has been made in the data field by the entry of data, the token valid flag 203 becomes "1", and when this entry is cancelled, the flag 203 becomes "0". When the read request token is delayed, delay flag 204 becomes "1". In a memory device such as 100b of FIG. 1a, as shown in FIG. 2a when a read request token 206 which corresponds to a particular address A arrives, the action of memory section 100b depends upon the condition of the valid flag in address A.
That is to say:
(1) When the valid flag is "1" then as shown in FIG. 2b, the data V stored in the data section of address A is read, entered into the token having the parameter Ra, and sent as the data token 207. PA0 (2) When the existing flag is "0" then the data intended for address A has not yet arrived, and the read request must therefore be stored. Referring to FIG. 2c, the read request token is stored in the field 207 (for example address Q) at the discretion of the delay management section 100c. For the sake of economic use of memory space, the read address parameter A is deleted and stored, but this deletion is in practice essentially not necessary. In these situations the information which shows that there is a first delay token in address A (shown by an asterisk in the drawings) is shown in a linking field 208. In the data field of address A in respect of which the delay has occurred the read request token store address pointer Q is stored. "1" is entered in the delay flag 204.
In this device many read request tokens can arrive which relate to the same address A of the memory section 100b. Therefore many tokens may be delayed relating to the same address, and as is shown in FIG. 3a the delayed tokens are stored in a series. Referring to FIGS. 3a and 3b, numerals 301 to 305 identify corresponding items to those identified by numerals 201 to 205 in FIGS. 2a to 2c. The series of fields stored in the delay management section 100c are used in the form of delay tokens. Thus when the write token 307 corresponding to the address A arrives, the series of delay tokens which are waiting for data to be entered in address A are all released as shown in FIG. 3b. When the token 307 arrives, the data V is entered in the data field of address A, and at the same time "1" is entered in valid flag 303 and "0" is entered in delay flag 304. The data V which is being entered in each address in the delay chain are correlated and data tokens 308 to 310 are formed and sent to the processing device. The addresses Q1 to Q3 which previously were used to store the delay tokens become free and can be used during subsequent delay processing.
In the above mentioned process it is not possible to manage new read request and write commands whilst managing the series of delay tokens, and this causes the process to be rather slow. This problem cannot be solved merely by separating the memory section 100b and the delay management section 100c and applying the process explained with reference to FIGS. 2a to 2c. Such a separation is illustrated in FIGS. 4a and 4b. With such an arrangement it is possible to have a memory section 100b and a delay management section 100c operating in parallel, but this poses problems of its own. These problems will be explained with reference to FIGS. 4a to 4e.
Numerals 401 to 404 in FIGS. 4a to 4e correspond to numerals 301 to 304 in FIGS. 3a and 3b, and indicate corresponding functions. Channels 409 and 410 carry tokens going from delay management section 100c to memory section 100b and from memory section 100b to delay management section 100c respectively. Referring to FIG. 4a, two read request tokens are shown as having been previously delayed. A further read request token 411 then arrives related to address A. In these circumstances the action of each part of the system is as described hereinbelow:
(1) Data has not yet been entered into address A, and thus the valid flag 403 of address A is "0". The read request token 411 must be delayed, and referring to FIG. 4b, it becomes delay token DREAD 412 and is sent to delay section 100c. At this time the parameter of address A is the leading address Q2 of the series of delay tokens which is maintained relating to address A.
(2) Referring to FIG. 4c, when the delay token 412 arrives at delay management device 100c, the token 412 is housed in an appropriate free address (for example Q3), and at the same time a new leading address token (NQA) 413 is output to memory device 100b. The token 413 has the purpose of delivering the new leading address Q3 of the series of delay tokens to the memory device 100b.
The new tokens DREAD and NQA which have appeared as described above are shown in FIG. 4f. Fields 751 to 754 in FIG. 4f correspond to fields 451 to 454 in FIG. 1b. The shaded sections of the diagram are fields which are not used.
Let us assume that token 413 arrives at memory section 100b at the same time as a new read request token 414 related to address A.
(3) If the token 413 arrives before token 414, the memory device 100b enters parameter Q3 into address A which is designated by token 413. Referring to FIG. 4d the pointer from address A designates the first token in the series, and token delay management is completed normally.
(4) If the token 413 arrives after token 414, then referring to FIG. 4e, token 414 is delayed and becomes token 411, and the parameter of delayed token 411 becomes the above new value Q2. Even if the token 411 is stored in delay management section 100c, two tokens are associated with the address Q2, and the delay tokens do not therefore form the normal series of single tokens.
It is an object of the present invention to obviate or mitigate the above-mentioned disadvantages of the prior art and make it possible to manage the operation of the memory device and the delay management device effectively.